package 左哥算法.ch07图;

import java.util.*;

public class Graph {
    public Map<Integer,Node> nodes;
    public Set<Edge> edges;

    public Graph() {
        nodes=new HashMap<>();
        edges=new HashSet<>();
    }

    public Graph(Map<Integer, Node> nodes, Set<Edge> edges) {
        this.nodes = nodes;
        this.edges = edges;
    }

    /**
     * 根据邻接矩阵数组生成图
     * @param arr：arr[a][a+1]：其中第一位是节点的值
     * 思路：
     *      先将所有节点放入nodes中
     *      再遍历节点能到哪些地方，为这些地方创建边，并增加入度出度
     */
    public Graph(Integer[][] arr) {
        this();
        for (Integer[] node : arr) {
            nodes.put(node[0],new Node(node[0]));
        }
        for (int i = 0; i < arr.length; i++) {
            Node node = nodes.get(arr[i][0]);
            for (int j = 1; j < arr[i].length; j++) {
                if (arr[i][j]==0){  //不能到达 j-1号点
                    continue;
                }
                Node next = nodes.get(arr[j - 1][0]);   //邻居节点
                //创建一条由当前节点通完邻居节点且边长为arr[i][j]的边
                Edge edge = new Edge(arr[i][j], node, next);
                edges.add(edge);
                node.out++;
                next.in++;
                node.nexts.add(next);
                node.edges.add(edge);
            }
        }
    }
}
